import java.util.*;

public class Solution {
    public static void main(String[] args) {
        /**
         * 测试代码*/
        Solution s = new Solution();
        int[] tasks = {3,2,1};
        int[] workers = {0,3,3};
        int pills = 1;
        int strength = 1;
        System.out.println(s.maxTaskAssign(tasks, workers, pills, strength));
    }

    public int maxTaskAssign1(int[] tasks, int[] workers, int pills, int strength) {
        /**
         * 你可以安排的最多任务数目
         * 明天再写，逻辑有点复杂
         * // 第三版：逻辑正确，但超时*/
        // 1 预处理
        int workLength = workers.length;
        // -排序
        Arrays.sort(tasks);
        Arrays.sort(workers);
        // -任务表使用链表进行存储，便于后续出（匹配一个出，不再记录下标）
        LinkedList<Integer> tasksByLinked = new LinkedList<>();
        for(int e: tasks) {
            tasksByLinked.add(e);
        }

        // 2 匹配
        // -创建备用数组，存储不能完成匹配的工人，后续尝试吃药匹配
        LinkedList<Integer> standby = new LinkedList<>();
        // -正常匹配（min工人 由大到小匹配 max任务）
        int w = 0;
        int count = 0;
        while(w < workLength && tasksByLinked.size() != 0) {
            // -1 工人由小到大匹配，每次匹配恰好值（右边界，工人力量>=任务所需）
            int index = searchRightRegion(tasksByLinked, workers[w]);

            // -2 判断
            if(index != -1) {
                // -可匹配
                count ++;
                tasksByLinked.remove(index);
                w ++;
            } else {
                // -不可匹配，将工人添加至备用队列中（由于本身有升序，我们只需头插，即可降序）
                standby.addFirst(workers[w]);
                w ++;
            }
        }

        // 3 中止处理
        if(tasksByLinked.size() == 0) {
            // -任务全部匹配完成，直接返回
            return count;
        } else {
            // -需要继续匹配（吃药）
            int cur = 0;
            while(pills > 0 && cur < standby.size() && tasksByLinked.size() != 0) {
                if(standby.get(0) + strength >= tasksByLinked.get(0)) {
                    // -可匹配
                    tasksByLinked.remove(0);
                    count ++;
                    cur ++;
                    pills --;
                } else {
                    // -最大值无法匹配，直接出
                    break;
                }
            }
        }

        // 4 返回值
        return count;
    }

    public int searchRightRegion(List<Integer> array, int target) {
        /**
         * 使用二分查找右边界，快速找到目标值*/
        // 1,查找
        int left = 0;
        int right = array.size() - 1;
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if(array.get(mid) <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        // 2,出来判断
        if(left == right && array.get(left) <= target) {
            return left;
        } else {
            return -1;
        }
    }

    public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
        /**
         * 你可以安排的最多任务数目
         * 明天再写，逻辑有点复杂
         * // 第四版：使用二分查找查找可能的最大任务数量*/
        // 1 预处理
        int workLength = workers.length;
        int taskLength = tasks.length;
        // -排升序
        Arrays.sort(tasks);
        Arrays.sort(workers);

        // 2 二分查找指定区间
        int left = 0;
        int right = Math.min(workLength, taskLength);
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if(checkEnable(tasks, workers, mid, pills, strength)) {
                // -可行
                left = mid;
            } else {
                // -不可行
                right = mid - 1;
            }
        }

        // 3 返回
        return left;
    }

    private boolean checkEnable(int[] tasks, int[] workers, int k, int p, int s) {
        /**
         * 判断是否可以完成k个任务
         * 逻辑：
         *  1，为了保证最大限度完成任务，故我们选取最强壮的k个工人 和 最简单的k个任务，保证其完成性
         *  2，*/
        // 1, 预处理
        // -创建数组维护指针
        int n = workers.length;
        int tasksIndex = 0;
        // -创建双端队列（保存当前值可匹配的任务项，小->大）
        Deque<Integer> queue = new LinkedList<>();
        // -计算吃药数量
        int count = 0;

        // 2,枚举工人处理任务
        for(int i = n-k; i < n; i++) {
            // -1 搜索可匹配项
            while(tasksIndex < k && workers[i] >= tasks[tasksIndex]) {
                // -入队并步进
                queue.offerLast(tasks[tasksIndex]);
                tasksIndex ++;
            }

            // -2 判断队列是否为空（为空：无匹配项则必须吃药 不为空：尝试匹配队头，无法匹配则必须吃药）
            if(!queue.isEmpty() && queue.peekFirst() <= workers[i]) {
                // -可以匹配，出对应的队头元素
                queue.pollFirst();
            } else {
                // -3 必须吃药
                count ++;
                // -3.1 吃药后再搜索匹配项
                while(tasksIndex < k && workers[i] + s >= tasks[tasksIndex]) {
                    // -入队并步进
                    queue.offerLast(tasks[tasksIndex]);
                    tasksIndex ++;
                }

                // -3.2 匹配队尾元素（两种情况：1 吃药后搜索到了元素，则出队尾也就是最大的更划算 2 没有搜索到元素，队不为空选择队尾，为空返回）
                if(!queue.isEmpty() && queue.peekFirst() <= workers[i] + s) {
                    queue.pollLast();
                } else {
                    // -该情况为单独无法匹配，吃药后也无法匹配
                    return false;
                }
            }
        }

        // 3, 判断用掉的药（不超过即可）
        return count <= p;
    }
}
